#ifndef _K_LINK_LIST_
#define _K_LINK_LIST_

template<typename T>
class LinkList
{
public:
	class LinkNode
	{
	public:
		LinkNode *next;
		T	value;
	};

	class BaseIterator
	{
	private:
		LinkList *m_list;
		LinkNode *m_prev;
		LinkNode *m_ThisNode;
	protected:
		inline T& GetValue() const {return this->m_ThisNode->value;}
	public:
		friend class LinkList;

		BaseIterator(): m_list(NULL), m_prev(NULL), m_ThisNode(NULL){}

		BaseIterator(LinkList *list, LinkNode *prev, LinkNode *ThisNode): 
		m_list(list), 
			m_prev(prev), 
			m_ThisNode(ThisNode){}

		BaseIterator(const BaseIterator& src): 
		m_list(src.m_list), 
			m_prev(src.m_prev), 
			m_ThisNode(src.m_ThisNode){};

		inline BaseIterator& operator=(const BaseIterator& src)
		{
			this->m_list = src.m_list;
			this->m_prev = src.m_prev;
			this->m_ThisNode = src.m_ThisNode;
			return (*this);
		}

		inline BaseIterator& operator++()
		{
			this->m_prev = this->m_ThisNode;
			this->m_ThisNode = this->m_ThisNode->next;
			return (*this);
		}

		inline BOOL operator!=(const BaseIterator& other)
		{
			return (this->m_ThisNode != other.m_ThisNode);
		}

		void erase()
		{
			m_list->erase(*this);
		}
	};

	class iterator: public BaseIterator
	{
	public:
		iterator(): BaseIterator(){}

		iterator(LinkList *list, LinkNode *prev, LinkNode *ThisNode): 
		BaseIterator(list, prev, ThisNode){}

		T& operator*() const
		{
			return this->GetValue();
		}

		iterator& operator++()
		{
			BaseIterator::operator++();
			return (*this);
		}

		iterator& operator++(int)
		{
			BaseIterator::operator++();
			return (*this);
		}

		BOOL operator!=(const iterator& other) 
		{
			return BaseIterator::operator!=(other);
		}
	};

	class const_iterator: public BaseIterator
	{
	public:
		const_iterator(): BaseIterator(){}

		const_iterator(LinkList *list, LinkNode *prev, LinkNode *ThisNode): BaseIterator(list, prev, ThisNode){}

		const_iterator(const iterator& src): BaseIterator(src){}

		const_iterator& operator=(const iterator& src)
		{
			BaseIterator::operator=(src);
			return (*this);
		}

		const T& operator*() const
		{
			return this->GetValue();
		}

		const_iterator& operator++()
		{
			BaseIterator::operator++();
			return (*this);
		}

		const_iterator& operator++(int)
		{
			BaseIterator::operator++();
			return (*this);
		}

		BOOL operator!=(const const_iterator& other) 
		{
			return BaseIterator::operator!=(other);
		}
	};

private:
	LinkNode *m_first;
	LinkNode *m_last;
	size_t m_count;
	static iterator iterator_end; 
	static const_iterator const_iterator_end; 
public:
	LinkList(): m_first(NULL), m_last(NULL), m_count(0) {}
	~LinkList(){ clear(); }

	inline LinkNode* GetFirst() const {return m_first;}
	inline LinkNode* GetLast() const {return m_last;}
	inline size_t GetCount() const {return m_count;}

	LinkNode* PushFront(const T value)
	{
		LinkNode *result = new LinkNode;
		result->next = m_first;
		result->value = value;

		m_first = result;

		if (!m_last)
			m_last = result;

		++m_count;

		return result;
	}

	LinkNode* PushBack(const T value)
	{
		LinkNode *result = new LinkNode;
		result->value = value;
		result->next = NULL;

		if (m_last)
			m_last->next = result;

		m_last = result;

		if (!m_first)
			m_first = result;

		++m_count;

		return result;
	}

	T pop()
	{
		assert(m_count);

		LinkNode *tmp = m_first;

		T result = m_first->value;

		m_first = tmp->next;

		if (m_last == tmp)
			m_last = NULL;

		delete tmp;

		return result;
	}

	void clear()
	{
		while (m_first)
		{
			LinkNode *tmp = m_first;
			m_first = tmp->next;
			delete tmp;
		}

		m_last = NULL;
		m_count = 0;
	}

	LinkNode* erase(LinkNode *prev, LinkNode *cur)
	{
		if (cur)
		{
			LinkNode *next = cur->next;

			if (prev)
				prev->next = next;
			else
				m_first = next;

			if (!next)
				m_last = prev;

			delete cur;

			return next;
		}
		else 
			return NULL;
	}

	void erase(const_iterator&)
	{

		if (cur)
		{
			LinkNode *next = cur->next;

			if (prev)
				prev->next = next;
			else
				m_first = next;

			if (!next)
				m_last = prev;

			delete cur;
		}
	}

	iterator begin() 
	{
		return iterator(this, NULL, m_first);
	}

	const iterator& end() 
	{
		return LinkList<T>::iterator_end;
	}
};

template<class T>
typename LinkList<T>::iterator LinkList<T>::iterator_end(NULL, NULL, NULL);

template<class T>
typename LinkList<T>::const_iterator LinkList<T>::const_iterator_end(NULL, NULL, NULL);

#endif	//_K_LINK_LIST_